The present invention relates to decoding apparatus, decoding methods, program-recording mediums, programs and recording/reproduction apparatus. More particularly, the present invention relates to a decoding apparatus capable of keeping up with a plurality of operating modes without increasing a circuit size, a decoding method adopted by the decoding apparatus, a program implementing the decoding method, a program-recording medium for storing the program and a recording/reproduction apparatus employing the decoding apparatus.
The capability exhibited by a contemporary recording/reproduction apparatus designed for optical disks as a capability of recording data into the optical disks mounted on the recording/reproduction apparatus has been becoming better remarkably. The conventional binary identification only is not sufficient means for guaranteeing a low reproduction-error rate. The number of cases has been increasing as cases in which a Viterbi decoding circuit capable of guaranteeing a low reproduction-error rate in spite of existence of inter-code interferences is used.
FIG. 1 is a diagram showing a typical configuration of a recording/reproduction apparatus employing the Viterbi decoding circuit.
In the typical configuration shown in FIG. 1, a modulation circuit 11 carries out a modulation process as part of processing to record data onto a recording medium 14. The modulation circuit 11 converts an input sequence received from a preceding stage not shown in the figure as a sequence of pieces of information to be recorded into a modulated sequence Xt (t=0, 1, 2 and so on), and outputs the modulated sequence Xt to a precoder 12.
The precoder 12 carries out a preceding process for a partial response, which is abbreviated hereafter to a PR. That is to say, the precoder 12 encodes the modulated sequence Xt received from the modulation circuit 11 on the basis of a predetermined coding rule to generate an intermediate sequence yt. The precoder 12 then records the intermediate sequence yt onto the recording medium 14 by way of a recording amplifier 13 including a recording head.
The recording medium 14 is typically an optical disk such as a Blu-ray Disc, a CD-RW (Compact Disk ReWritable) or a DVD±RW (Digital Versatile Disk ReWritable). The recording amplifier 13 records data received by the modulation circuit 11 from the preceding stage not shown in the figure as a sequence of pieces of information to be recorded onto the recording medium 14.
A reproduction amplifier 15 including a reproduction head detects a signal reproduced from the recording medium 14 and outputs the result of the detection to an equalizer 16. The equalizer 16 carries out an equalization process for a target transmission line model close to the frequency characteristic of a transmission line on the reproduced signal received from the reproduction amplifier 15 to generate a transmission-line output Z. An example of the equalization process is a PR equalization process. Then, the equalizer 16 outputs the transmission-line output Z to a PLL (Phase Locked Loop) 17 and a sampling circuit 18.
The PLL 17 extracts clock components from the transmission-line output Z on a transmission line including the recording medium 14 to generate a clock signal synchronized with the reproduced signal. The PLL 17 then outputs the generated clock signal to the sampling circuit 18, a Viterbi decoding circuit 19 and a demodulation circuit 20.
The sampling circuit 18 samples the transmission-line output Z received from the equalizer 16 in synchronization with the clock signal received from the PLL 17 to convert the transmission-line output Z into data, which is shown in the figure as a sampled sequence Zt. The sampling circuit 18 then supplies the sampled sequence Zt to the Viterbi decoding circuit 19. The Viterbi decoding circuit 19 carries out a Viterbi decoding process on the sampled sequence Zt received from the sampling circuit 18 to produce a most probable modulated sequence xt corresponding to the output of the modulation circuit 11.
The demodulation circuit 20 is the counterpart of the modulation circuit 11. The demodulation circuit 20 demodulates the most probable modulated sequence xt received from the Viterbi decoding circuit 19 and outputs the result of the demodulation process to a succeeding stage not shown in the figure.
FIG. 2 is a diagram showing a typical configuration of the Viterbi decoding circuit 19 employed in the recording/reproduction apparatus shown in FIG. 1.
As shown in FIG. 2, the typical configuration of the Viterbi decoding circuit 19 comprises a BM (Branch Metric) computation circuit 41, an ACS (Add, Compare and Select) circuit 42, a path memory 43 and a most-probable determination circuit 44.
The BM computation circuit 41 uses the sampled sequence Zt received as an input signal to compute branch-metric data for state transitions, which are each a transition from a state to another, and outputs the branch-metric data to the ACS circuit 42.
The ACS circuit 42 adds path-metric data of a state immediately preceding the present state to the branch-metric data received from the BM computation circuit 41 to produce a sum. If paths merge at the path memory 43 to be described later, the ACS circuit 42 adds path-metric data of a state immediately preceding the present state to the branch-metric data received from the BM computation circuit 41 to produce a sum for each of the merging paths, and compares the sums with each other to select the smallest one. The ACS circuit 42 then uses the selected sum resulting from of the addition, comparison and selection processes as updated path-metric data of the present state. Finally, the ACS circuit 42 outputs the result of the selection of the sums to the path memory 43 and the most-probable determination circuit 44. In the following description, the path-metric data may be referred to simply as metric data in some cases.
The path memory 43 is a plurality of shift registers provided at a plurality of stages each identified by a stage number as registers each composed of an array of flip-flops. Each of the flip-flops serves as a memory. A value stored in a memory is subjected to a select-shift operation before being shifted to a next memory. To put it in detail, a value to be stored in a memory provided at any specific stage is selected among values, which are received from memories provided at a stage preceding the specific stage through merging paths cited above, in dependence on the aforementioned selection result received from the ACS circuit 42, and the selected value is then stored in the memory before being shifted to memories provided at a stage immediately following the specific stage. These operations to select, store and shift a value are carried out repeatedly. The operation to select a value to be stored in a memory provided at any specific stage among values from memories at a stage preceding the specific stage in dependence on the aforementioned selection result received from the ACS circuit 42 agrees with the operation carried out by the ACS circuit 42 to select a smallest sum among sums computed for merging paths as described above.
The most-probable determination circuit 44 fetches an output signal from memories provided at the last stage and supplies the fetched output signal to the demodulation circuit 20 as the modulated sequence xt. For example, assume that the path memory 43 is composed of 16 stages. In this case, the most-probable determination circuit 44 fetches an output signal from memories composing a shift register provided at the 16th stage. In this way, the most probable signal reproduced at a time leading ahead of the present time by 16 clocks is firmly determined.
It is to be noted that, if the above operation to select a value is not carried out in the path memory 43 as an operation agreeing with merging of paths, the most-probable determination circuit 44 carries out a most probable determination process to extract an output signal from path memories for storing minimum path-metric data for a state on the basis of a selection result received the ACS circuit 42, and supplies the output signal extracted in the most probable determination process to the demodulation circuit 20 as the modulated sequence xt.
By referring to FIGS. 3 and 4, the following description explains a PR transmission line for a case in which (1, 7) RLL (Run Length Limited) codes for d (minimum run length)=1 are used. It is to be noted that, in the typical configurations shown in FIGS. 3 and 4, a circle represents a state whereas a label attached to an arrow represents a branch or a transition. An RLL code is a code in which the number of 0s sandwiched between is in a modulated code is limited. A (d, k) RLL code is an RLL code with a minimum run length d set for a sequence of 0s sandwiched between 1s and a maximum run length k set for the sequence of 0s sandwiched between 1s. For example, a (1, 7) RLL code has a minimum run length of 1 and a maximum run length of 7 for the sequence of 0s sandwiched between 1s.
FIG. 3 is a diagram showing state transitions of a PR (1, x, 1) transmission line with a constraint length of 3 for a case in which (1, 7) RLL codes are used. It is to be noted that the PR (1, x, 1) transmission line with a constraint length of 3 can be typically a PR (1, 1, 1) transmission line or a PR (1, 2, 1) transmission line. Since these typical transmission lines are different from each other only in that they have different theoretical values (or identification reference values) of transitions c, they are all explained below as the PR (1, x, 1) transmission line.
In the case of the typical configuration shown in FIG. 3, notation c000 denotes a transition from state S00 to state S00. Notation c001 denotes a transition from state S00 to state S01. Notation c011 denotes a transition from state S01 to state S11. Notation c111 denotes a transition from state S11 to state S11. Notation c110 denotes a transition from state S11 to state S10. Notation c100 denotes a transition from state S10 to state S00.
That is to say, in the diagram showing state transitions of a PR (1, x, 1) transmission line with a constraint length of 3, d (minimum run length)=1 shrinks the number of state transitions to 4 and the number of states to 4.
FIG. 4 is a diagram showing transitions of states of a PR (1, x, x, 1) transmission line with a constraint length of 4 for a case in which (1, 7) RLL codes are used. It is to be noted that the PR (1, x, x, 1) transmission line with a constraint length of 4 can be typically a PR (1, 2, 2, 1) transmission line or a PR (1, 3, 3, 1) transmission line. Since these typical transmission lines are different from each other only in that they have different theoretical values (or identification reference values) of transitions c, they are all explained below as the PR (1, x, x, 1) transmission line.
In the case of the typical configuration shown in FIG. 4, notation c0000 denotes a transition from state S000 to state S000. Notation c0001 denotes a transition from state S000 to state S001. Notation c0011 denotes a transition from state S001 to state S011. Notation c0111 denotes a transition from state S011 to state S111. Notation c0110 denotes a transition from state S011 to state S110. Notation c1111 denotes a transition from state S111 to state S111. Notation c1110 denotes a transition from state S111 to state S110. Notation c0011 denotes a transition from state S110 to state S100. Notation c1001 denotes a transition from state S100 to state S001. Notation c1000 denotes a transition from state S100 to state S000.
That is to say, in the diagram showing transitions of states of a PR (1, x, x, 1) transmission line with a constraint length of 4, d (minimum run length)=1 shrinks the number of values to 7 and the number of states to 6.
As described above, in a PR transmission line, a reproduced signal value is not confirmed by a state S itself. Instead, it is not until a transition c from a state S to a state S that a reproduced signal value is identified firmly.
By referring to FIGS. 5 and 6, the following description explains details of the Viterbi decoding circuit 19 for the PR (1, x, 1) transmission line, the state transitions of which are shown in FIG. 3. It is to be noted that FIG. 5 is a diagram showing typical configurations of the branch-metric computation circuit 41 and the ACS circuit 42 for the PR (1, x, 1) transmission line, the state transitions of which are shown in FIG. 3. On the other hand, FIG. 6 is a diagram showing a typical configuration of the path memory 43 for the PR (1, x, 1) transmission line, the state transitions of which are shown in FIG. 3.
In the typical configuration shown in FIG. 5, the branch-metric computation circuit 41 includes as many branch-metric computation sections 61, which are used for computing BM (branch-metric data) for every transition from a state to another, as the state transitions. In the case of the typical configuration shown in FIG. 5, the number of state transitions is 6. Thus, the branch-metric computation circuit 41 includes 6 branch-metric computation sections 61-1 to 61-6. Each of the branch-metric computation sections 61-1 to 61-6 calculates branch-metric data bm representing the likelihood of a state transition c and outputs the branch-metric data bm to the ACS circuit 42. It is to be noted that symbol cABC (where suffixes A, B and C each represent the integer 0 or 1) assigned to a state transition c denotes the theoretical value (the identification reference value) of the state transition c. In addition, symbol n^2 used in the following description denotes the square of n.
To put it concretely, let us assume that a reproduced signal (or a sampled sequence) completing a PR equalization at a time k is zk. In this case, the branch-metric computation section 61-1 computes branch-metric data bm000k (=(zk−c000)^2), which represents the likelihood of the state transition c000, and outputs the branch-metric data bm000k to an ACS section 62-1. By the same token, the branch-metric computation section 61-2 computes branch-metric data bm100k (=(zk−c100)^2), which represents the likelihood of the state transition c100, and outputs the branch-metric data bm100k also to the ACS section 62-1. In the same way, the branch-metric computation section 61-3 computes branch-metric data bm001k (=(zk−c001)^2), which represents the likelihood of the state transition c001, and outputs the branch-metric data bm001k to an ACS section 62-2. Likewise, the branch-metric computation section 61-4 computes branch-metric data bm110k (=(zk−c110)^2), which represents the likelihood of the state transition c110, and outputs the branch-metric data bm110k to an ACS section 62-3. Similarly, the branch-metric computation section 61-5 computes branch-metric data bm001k (=(zk−c011) ^2) which represents the likelihood of the state transition c011, and outputs the branch-metric data bm001k to an ACS section 62-4. By the same token, the branch-metric computation section 61-6 computes branch-metric data bm111k (=(zk−c111)^2), which represents the likelihood of the state transition c111, and outputs the branch-metric data bm111k also to the ACS section 62-4.
The ACS circuit 42 adds path-metric data stored internally as path-metric data of a state immediately preceding the present state to the branch-metric data received from the branch-metric computation circuit 41 to produce a sum. The ACS circuit 42 then uses the sum as updated path-metric data m of the present state. The path-metric data m is the likelihood of a history up to state S. The ACS circuit 42 includes as many ACS (add, compare and select) sections 62 as states. In the case of the typical configuration shown in FIG. 5, the number of states is 4. Thus, the ACS circuit 42 includes 4 ACS sections 62-1 to 62-4. It is to be noted that the ACS sections 62-1 to 62-4 with path merging existing each compare the sum of path-metric data of a state immediately preceding the present state for one path and the branch-metric data with the sum of path-metric data of a state immediately preceding the present state for the other path and the branch-metric data, selecting the smaller one. The ACS circuit 42 then uses the selected smaller sum as updated path-metric data of the present state. Finally, the ACS circuit 42 outputs a selection result indicating which sum has been selected to the path memory 43.
To put it concretely, the ACS section 62-1 updates the path-metric data m00k, which is the likelihood of a history up to state S00. To be more specific, the ACS section 62-1 adds the path-metric data m00k-1 stored internally in the ACS section 62-1 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm000k received from the branch-metric computation section 61-1 to produce a first sum. The ACS section 62-1 also adds the path-metric data m10k-1 stored internally in the ACS section 62-3 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm100k received from the branch-metric computation section 61-2 to produce a second sum. Then, the ACS section 62-1 compares the first and second sums with each other in order to select the smaller one to be used as updated path-metric data m00k of the present state. Finally, the ACS section 62-1 outputs a selection result sel00 to a memory included in the path memory 43 as a memory used for storing the value of state S00. The computations and the comparison, which are carried out by the ACS section 62-1, can be expressed by Eq. (1) given as follows:m00k=min {m00k-1+bm000k,m10k-1+bm100k}  (1)
On the other hand, the ACS section 62-2 updates the path-metric data m01k, which is the likelihood of a history up to state S01. To put it concretely, the ACS section 62-2 adds the path-metric data m00k-1 stored internally in the ACS section 62-1 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm001k received from the branch-metric computation section 61-3 to produce a sum and uses the sum as updated path-metric data m01k of the present state. The computation carried out by the ACS section 62-2 can be expressed by Eq. (2) given as follows:m01k=m00k-1+bm001k  (2)
By the same token, the ACS section 62-3 updates the path-metric data m10k, which is the likelihood of a history up to state S10. To put it concretely, the ACS section 62-3 adds the path-metric data m11k-1 stored internally in the ACS section 62-4 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm110k received from the branch-metric computation section 61-4 to produce a sum and uses the sum as updated path-metric data m10k of the present state. The computation carried out by the ACS section 62-3 can be expressed by Eq. (3) given as follows:m10k=m11k-1+bm110k  (3)
In the same way as the ACS section 62-1, the ACS section 62-4 updates the path-metric data m11k, which is the likelihood of a history up to state S11. To put it concretely, the ACS section 62-4 adds the path-metric data m01k-1 stored internally in the ACS section 62-2 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm011k received from the branch-metric computation section 61-5 to produce a first sum. The ACS section 62-4 also adds the path-metric data m11k-1 stored internally in the ACS section 62-4 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm111k received from the branch-metric computation section 61-6 to produce a second sum. Then, the ACS section 62-4 compares the first and second sums in order to select the smaller one to be used as updated path-metric data m11k of the present state. Finally, the ACS section 62-4 outputs a selection result sel11 to a memory included in the path memory 43 as a memory used for storing the value of state S11. The computations and the comparison, which are carried out by the ACS section 62-4, can be expressed by Eq. (4) given as follows:m11k=min {m11k-1+bm111k,m01k-1+bm011k}  (4)
The path memory 43 shown in FIG. 6 depicts a trellis expressing the state-transition diagram shown in FIG. 3 in terms of sequences along the time axis. A circle represents a state S shown in FIG. 3 whereas an arrow represents a state transition c. Each shift register employed in the path memory 43 shown in FIG. 6 has 4 memories having the same form as the 4-state trellis expressing the state-transition diagram shown in FIG. 3 in terms of sequences along the time axis. That is to say, the Viterbi decoding circuit 19 for a PR (1, x, 1) transmission line carries out a decoding process on the basis of the trellis expressing the state-transition diagram shown in FIG. 3 in terms of sequences along the time axis.
Thus, a circle in the path memory 43 also represents a memory such as a flip-flop. In the typical configuration shown in FIG. 6, the number of stages of memories composing the path memory 43 is 3. It is to be noted, however, that the number of stages can be actually 16 or 32 for example.
In the path memory 43, an operation to select a value among values stored in memories at a preceding stage is carried out in dependence on a selection result, which is the result of selection carried out by the ACS circuit 42, and the selected value is shifted to a memory at the stage immediately following the preceding stage repeatedly. To put it concretely, in the path memory 43, a value to be stored in a memory for state S00 at any specific stage is a value selected among a value stored in a memory for state S00 at a stage immediately preceding the specific stage and a value stored in a memory for state S10 at the stage immediately preceding the specific stage in accordance with a selection result sel00 received from the ACS section 62-1. The selected value stored in the memory for state S00 at the specific stage is then shifted (output) to a memory for state S00 at a stage immediately following the specific stage and a memory for state S01 at the stage immediately following the specific stage. By the same token, in the path memory 43, a value to be stored in a memory for state S11 at the specific stage is a value selected among a value stored in a memory for state S11 at the stage immediately preceding the specific stage and a value stored in a memory for state S01 at the stage immediately preceding the specific stage in accordance with a selection result sel11 received from the ACS section 62-4. The selected value stored in the memory for state S11 at the specific stage is then shifted (output) to a memory for state S11 at the stage immediately following the specific stage and a memory for state S10 at the stage immediately following the specific stage.
It is to be noted that, by way of a memory for state S01 at each specific stage, a value is shifted from a memory at a stage immediately preceding the specific stage to a memory existing at a stage immediately following the specific stage as a memory according to a transition c. Thus, for any specific stage in the path memory 43, a value stored in a memory for state S00 at a stage immediately preceding the specific stage is shifted to a memory for state S11 at a stage immediately following the specific stage by way of a memory for state S01 at the specific stage. By the same token, by way of a memory for state S10 at each specific stage, a value is shifted from a memory at a stage immediately preceding the specific stage to a memory existing at a stage immediately following the specific stage as a memory according to a transition c. Thus, for any specific stage in the path memory 43, a value stored in a memory for state S11 at a stage immediately preceding the specific stage is shifted to a memory for state S00 at a stage immediately following the specific stage by way of a memory for state S10 at the specific stage.
As described above, a value to be stored in any path memory provided at any specific stage identified by a certain stage number as a path memory at which paths merge is selected among values stored in path memories provided at stages immediately following the specific stage in accordance with a selection result produced by a process carried out by the ACS circuit to select a sum of metric data as a result of comparison of sums. As a result, the most-probable determination circuit 44 fetches data originated from the most probable paths from memories provided at the last stage, and supplies the fetched data to the demodulation circuit 20 as the modulated sequence xt.
By referring to FIGS. 7 and 8, the following description explains details of the Viterbi decoding circuit 19 for the PR (1, x, x, 1) transmission line, the state transitions of which are shown in FIG. 4. It is to be noted that FIG. 7 is a diagram showing typical configurations of the branch-metric computation circuit 41 and the ACS circuit 42 for the PR (1, x, x, 1) transmission line, the state transitions of which are shown in FIG. 4. On the other hand, FIG. 8 is a diagram showing a typical configuration of the path memory 43 for the PR (1, x, x, 1) transmission line, the state transitions of which are shown in FIG. 4. The typical configurations shown in FIGS. 7 and 8 are basically the same as their counterparts included in the Viterbi decoding circuit 19 as shown in FIGS. 5 and 6 respectively except that, in the typical configurations shown in FIGS. 7 and 8, the number of states is 6 and the number of state transitions is 10. Thus, descriptions of their details are not repeated to avoid duplications.
In the typical configuration shown in FIG. 7, the branch-metric computation circuit 41 includes as many branch-metric computation sections 71 as the state transitions. In the case of the typical configuration shown in FIG. 7, the number of state transitions is 10. Thus, the branch-metric computation circuit 41 includes 10 computation sections 71-1 to 71-10.
The branch-metric computation section 71-1 computes branch-metric data bm0000k (=(zk−c0000)^2), which represents the likelihood of the state transition c0000, and outputs the branch-metric data bm0000k to an ACS section 72-1. By the same token, the branch-metric computation section 71-2 computes branch-metric data bm1000k (=(zk−c1000)^2), which represents the likelihood of the state transition c1000, and outputs the branch-metric data bm1000k also to the ACS section 72-1. Likewise, the branch-metric computation section 71-3 computes branch-metric data bm0001k (=(zk−c0001)^2), which represents the likelihood of the state transition c0001, and outputs the branch-metric data bm0001k to an ACS section 72-2. By the same token, the branch-metric computation section 71-4 computes branch-metric data bm1001k (=(zk−c1001)^2), which represents the likelihood of the state transition c1001, and outputs the branch-metric data bm1001k also to the ACS section 72-2. In the same way, the branch-metric computation section 71-5 computes branch-metric data bm0011k (=(zk−c0011)^2), which represents the likelihood of the state transition c0011, and outputs the branch-metric data bm0011k to an ACS section 72-3.
Likewise, the branch-metric computation section 71-6 computes branch-metric data bm1100k (=(zk−c1100)^2), which represents the likelihood of the state transition c1100, and outputs the branch-metric data bm1100k to an ACS section 72-4. Similarly, the branch-metric computation section 71-7 computes branch-metric data bm0110k (=(zk−c0110)^2), which represents the likelihood of the state transition c0110, and outputs the branch-metric data bm0110k to an ACS section 72-5. By the same token, the branch-metric computation section 71-8 computes branch-metric data bm1110k (=(zk−c1110)^2), which represents the likelihood of the state transition c1110, and outputs the branch-metric data bm1110k also to the ACS section 72-5. Similarly, the branch-metric computation section 71-9 computes branch-metric data bm0111k (=(zk−c0111)^2), which represents the likelihood of the state transition c0111, and outputs the branch-metric data bm0111k to an ACS section 72-6. By the same token, the branch-metric computation section 71-10 computes branch-metric data bm1111k (=(zk−c1111)^2), which represents the likelihood of the state transition c1111, and outputs the branch-metric data bm1111k also to the ACS section 72-6.
The ACS circuit 42 includes as many ACS (add, compare and select) sections 72 as states. In the case of the typical configuration shown in FIG. 7, the number of states is 6. Thus, the ACS circuit 42 includes 6 ACS sections 72-1 to 72-6.
The ACS section 72-1 updates path-metric data m000k, which is the likelihood of a history up to state S000. To be more specific, the ACS section 72-1 adds the path-metric data m000k-1 stored internally in the ACS section 72-1 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm0000k received from the branch-metric computation section 71-1 to produce a first sum. The ACS section 72-1 also adds the path-metric data m100k-1 stored internally in the ACS section 72-4 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm1000k received from the branch-metric computation section 71-2 to produce a second sum. Then, the ACS section 72-1 compares the first and second sums in order to select the smaller one to be used as updated path-metric data m000k of the present state. Finally, the ACS section 72-1 outputs a selection result sel000 to a memory included in the path memory 43 as a memory used for storing the value of state S000. The computation and the comparison, which are carried out by the ACS section 72-1, can be expressed by Eq. (5) given as follows:m000k=min {m000k-1+bm0000k, m100k-1+bm1000k}  (5)
By the same token, the ACS section 72-2 updates path-metric data m001k, which is the likelihood of a history up to state S001. To be more specific, the ACS section 72-2 adds the path-metric data m000k-1 stored internally in the ACS section 72-1 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm0001k received from the branch-metric computation section 71-3 to produce a first sum. The ACS section 72-2 also adds the path-metric data m100k-1 stored internally in the ACS section 72-4 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm1001k received from the branch-metric computation section 71-4 to produce a second sum. Then, the ACS section 72-2 compares the first and second sums in order to select the smaller one to be used as updated path-metric data m001k of the present state. Finally, the ACS section 72-2 outputs a selection result sel001 to a memory included in the path memory 43 as a memory used for storing the value of state S001. The computation and the comparison, which are carried out by the ACS section 72-2, can be expressed by Eq. (6) given as follows:m001k=min {m000k-1+bm0001k, m100k-1+bm1001k}  (6)
On the other hand, the ACS section 72-3 updates path-metric data m011k, which is the likelihood of a history up to state S011. To be more specific, the ACS section 72-3 adds the path-metric data m001k-1 stored internally in the ACS section 72-2 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm0011k received from the branch-metric computation section 71-5 to produce a sum. Then, the ACS section 72-3 uses the sum as updated path-metric data m011k of the present state. The computation carried out by the ACS section 72-3 can be expressed by Eq. (7) given as follows:m011k=m001k-1+bm0011k  (7)
By the same token, the ACS section 72-4 updates path-metric data m100k, which is the likelihood of a history up to state S100. To be more specific, the ACS section 72-4 adds the path-metric data m110k-1 stored internally in the ACS section 72-5 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm1100k received from the branch-metric computation section 71-6 to produce a sum. Then, the ACS section 72-4 uses the sum as updated path-metric data m100k of the present state. The computation carried out by the ACS section 72-4 can be expressed by Eq. (8) given as follows:m100k=m110k-1+bm1100k  (8)
The ACS section 72-5 updates path-metric data m110k, which is the likelihood of a history up to state S110. To be more specific, the ACS section 72-5 adds the path-metric data m111k-1 stored internally in the ACS section 72-6 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm1110k received from the branch-metric computation section 71-8 to produce a first sum. The ACS section 72-5 also adds the path-metric data m011k-1 stored internally in the ACS section 72-3 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm0110k received from the branch-metric computation section 71-7 to produce a second sum. Then, the ACS section 72-5 compares the first and second sums in order to select the smaller one to be used as updated path-metric data m110k of the present state. Finally, the ACS section 72-5 outputs a selection result sel110 to a memory included in the path memory 43 as a memory used for storing the value of state S110. The computation and the comparison, which are carried out by the ACS section 72-5, can be expressed by Eq. (9) given as follows:m110k=min {m111k-1+bm1110k, m011k-1+bm0110k}  (9)
By the same token, the ACS section 72-6 updates path-metric data m111k, which is the likelihood of a history up to state S111. To be more specific, the ACS section 72-6 adds the path-metric data m111k-1 stored internally in the ACS section 72-6 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm1111k received from the branch-metric computation section 71-10 to produce a first sum. The ACS section 72-6 also adds the path-metric data m011k-1 stored internally in the ACS section 72-3 as the path-metric data of the state immediately preceding the present state to the branch-metric data bm0111k received from the branch-metric computation section 71-9 to produce a second sum. Then, the ACS section 72-6 compares the first and second sums in order to select the smaller one to be used as updated path-metric data m111k of the present state. Finally, the ACS section 72-6 outputs a selection result sel111 to a memory included in the path memory 43 as a memory used for storing the value of state S111. The computation and the comparison, which are carried out by the ACS section 72-6, can be expressed by Eq. (10) given as follows:m111k=min {m111k-1+bm1111k, (m011k-1+bm0111k}  (10)
The path memory 43 shown in FIG. 8 depicts a trellis expressing the state-transition diagram shown in FIG. 4 in terms of sequences along the time axis. A circle represents a state S shown in FIG. 4 whereas an arrow represents a state transition c. Each shift register employed in the path memory 43 shown in FIG. 8 has 6 memories having the same form as the 6-state trellis expressing the state-transition diagram shown in FIG. 4 in terms of sequences along the time axis. That is to say, the Viterbi decoding circuit 19 for a PR (1, x, x, 1) transmission line carries out a decoding process on the basis of the trellis expressing the state-transition diagram shown in FIG. 4 in terms of sequences along the time axis.
In the path memory 43 shown in FIG. 8, an operation to select a value among values stored in memories at a preceding stage is carried out in dependence on the result of the selection carried out by the ACS circuit 42, and the selected value is shifted to a memory at the stage immediately following the preceding stage repeatedly. That is to say, in the path memory 43, a value to be stored in a memory for state S000 at any specific stage is a value selected among a value stored in a memory for state S000 at a stage immediately preceding the specific stage and a value stored in a memory for state S100 at the stage immediately preceding the specific stage in accordance with a selection result sel000 received from the ACS section 72-1. The selected value stored in the memory for state S000 at the specific stage is then shifted (output) to a memory for state S000 at a stage immediately following the specific stage and a memory for state S000 at the stage immediately following the specific stage. By the same token, in the path memory 43, a value to be stored in a memory for state S001 at the specific stage is a value selected among a value stored in a memory for state S000 at the stage immediately preceding the specific stage and a value stored in a memory for state S100 at the stage immediately preceding the specific stage in accordance with a selection result sel001 received from the ACS section 72-2. The selected value stored in the memory for state S001 at the specific stage is then shifted (output) to a memory for state S011 at the stage immediately following the specific stage.
In addition, in the path memory 43, a value to be stored in a memory for state S110 at any specific stage is a value selected among a value stored in a memory for state S011 at a stage immediately preceding the specific stage and a value stored in a memory for state S111 at the stage immediately preceding the specific stage in accordance with a selection result sel001 received from the ACS section 72-5. The selected value stored in the memory for state S110 at the specific stage is then shifted (output) to a memory for state S100 at a stage immediately following the specific stage. By the same token, in the path memory 43, a value to be stored in a memory for state S111 at the specific stage is a value selected among a value stored in a memory for state S011 at the stage immediately preceding the specific stage and a value stored in a memory for state S111 at the stage immediately preceding the specific stage in accordance with a selection result sel111 received from the ACS section 72-6. The selected value stored in the memory for state S111 at the specific stage is then shifted (output) to a memory for state S110 at the stage immediately following the specific stage and a memory for state S111 at the stage immediately following the specific stage.
It is to be noted that, by way of a memory for state S011 at each specific stage, a value is shifted from a memory at a stage immediately preceding the specific stage repeatedly to a memory existing at a stage immediately following the specific stage as a memory according to a transition c. Thus, for any specific stage in the path memory 43, a value stored in a memory for state S001 at a stage immediately preceding the specific stage is shifted to a memory for state S110 at a stage immediately following the specific stage and a memory for state S111 at the same following stage by way of a memory for state S011 at the specific stage. By the same token, by way of a memory for state S100 at each specific stage, a value is shifted from a memory at a stage immediately preceding the specific stage repeatedly to a memory existing at a stage immediately following the specific stage as a memory according to a transition c. Thus, for any specific stage in the path memory 43, a value stored in a memory for state S110 at a stage immediately preceding the specific stage is shifted to a memory for state S000 at a stage immediately following the specific stage and a memory for state S001 at the same following stage by way of a memory for state S100 at the specific stage.
As is obvious from the above descriptions, the branch-metric computation circuit 41, the ACS circuit 42 and the path memory 43 each have different configurations for different constraint lengths, that is, different state counts. In general, the smaller the d (minimum run length) and the larger the constraint length, the larger the size of the circuit.
However, a change in constraint length or a change in inter-code interference length is attributed to a change of the frequency characteristic of the PR transmission line and, normally, if the structure of the recording medium as well as the structure of the recording head are determined, an optimum PRML (Partial Response Maximum Likelihood) method is generally determined to be a method of a certain type.
On the other hand, a demand for downward compatibility with specifications of the optical disk, which has been becoming popular so far, is also high. In addition, even for the same generation, a plurality of specification sets exists so that a recording/reproduction apparatus for recent optical disks is required absolutely to keep up with different specifications of frequency characteristics. The specification sets include specifications for disks of addition-recording and renewal-recording types, single-layer and multiple-layer disks as well as low-density and high-density disks.
For the reasons described above, a single recording/reproduction apparatus is required to have a plurality of operating modes for different constraint lengths such as PR (1, 2, 1) and PR (1, 3, 3, 1). Thus, it is necessary to provide such a single recording/reproduction apparatus with a plurality of Viterbi decoding circuits of different types having different constraint lengths and use the apparatus by switching the Viterbi decoding circuit from one having a certain constraint length to another having a different constraint length. In addition, it is necessary to also provide a branch-metric computation circuit 41, an ACS circuit 42 and a path memory 43, which have been explained by referring to FIGS. 5 to 8, for each type having a constraint length. If a single recording/reproduction apparatus needs to be provided with a plurality of operating modes for different constraint lengths as described above, however, the recording/reproduction apparatus will have a problem of a large size of the circuit or a problem of limitation on the type of the Viterbi decoding circuit.
In addition, high speed operations are required also in a Viterbi decoding circuit employed in the recording/reproduction apparatus in order to meet a higher demand raised in recent years as a demand for a high recording/reproduction rate. A portion determining the operating speed of a Viterbi decoding circuit is the ACS circuit for carrying out addition, subtraction (or comparison) and comparison operations in a short possible period such as 1 clock cycle. In addition, if the subtraction (or comparison) processing carried out by the ACS circuit as processing having an amount corresponding to a plurality of clock cycles can all be completed in a time slot, the operating speed can be further increased due to such early completion. The portion determining the operating speed of a Viterbi decoding circuit is referred to as a critical path.
Japanese Patent Laid-open No. Hei 8-84082 discloses a proposed technique to increase the operating speed by at least two times by handling state transitions occurring during at least two time slots as one state transition occurring in one time slot. In this case, however, the size of the circuit must be increased by up to two times in exchange for the increase in operating speed.
By referring to FIGS. 9 to 12, the following description explains a Viterbi decoding circuit 19 having its operating speed increased by carrying out processing of the amount corresponding to two time slots in just one time slot.
FIGS. 9 and 10 are diagrams showing a Viterbi decoding circuit 19 provided for the PR (1, x, 1) transmission line shown in FIG. 3 as a Viterbi decoding circuit 19 capable of carrying out processing of the amount corresponding to two time slots in just one time slot. That is to say, the Viterbi decoding circuit 19 shown in FIGS. 9 and 10 is capable of carrying out processing, which is performed by the Viterbi decoding circuit 19 shown in FIGS. 5 and 6 in two time slots, in just one time slot.
In the typical configuration shown in FIG. 9, the branch-metric computation circuit 41 has branch-metric computation sections 81-1 to 81-10 each used for calculating branch-metric data for state transitions occurring over two time slots in the configuration shown in FIG. 5. Each of the branch-metric computation sections 81-1 to 81-10 computes branch-metric data bm for state transitions occurring over two time slots and outputs the branch-metric data bm to an ACS circuit 42. That is to say, the branch-metric computation circuit 41 shown in FIG. 9 computes branch-metric data bmABCDk (=bmABCk-1+bmBCDk) where bmABCk-1 is equal to the square (zk-1−cABC)^2, bmBCDk is equal to the square (zk−cBCD)^2 whereas suffixes A, B, C and D are each the integer 0 or 1.
To put it concretely, the branch-metric computation section 81-1 computes branch-metric data bm0000k (=bm000k-1+bm000k) where branch-metric data bm000k-1 is equal to the square (zk-1−c000)^2 and branch-metric data bm000k is equal to the square (zk−c000)^2, outputting the branch-metric data bm0000k to the ACS section 82-1. In this case, notation bm0000k denotes branch-metric data corresponding to a state transition occurring over two time slots, notation bm000k denotes branch-metric data corresponding to a state transition from a state immediately preceding the present state and notation bm0000k-1 denotes branch-metric data corresponding to a state transition from a state immediately leading ahead of the state immediately preceding the present state.
In the following description, bmABCk-1 is equal to the square (zk-1−cABC)^2, bmBCDk is equal to the square (zk−cBCD)^2 whereas suffixes A, B, C and D are each the integer 0 or 1 as described above. Thus, by the same token, the branch-metric computation section 81-2 computes branch-metric data bm1000k (=bm100k-1+bm000k) and outputs the branch-metric data bm1000k also to the ACS section 82-1 where notation bm1000k denotes branch-metric data corresponding to a state transition occurring over two time slots. In the same way, the branch-metric computation section 81-3 computes branch-metric data bm1100k (=bm110k-1+bm100k) and outputs the branch-metric data bm1100k also to the ACS section 82-1 where notation bm1100k denotes branch-metric data corresponding to a state transition occurring over two time slots.
Similarly, the branch-metric computation section 81-4 computes branch-metric data bm0001k(=bm000k-1+bm001k) and outputs the branch-metric data bm0001k to the ACS section 82-2 where notation bm0001k denotes branch-metric data corresponding to a state transition occurring over two time slots. Likewise, the branch-metric computation section 81-5 computes branch-metric data bm1001k (=bm100k-1+bm001k) and outputs the branch-metric data bm1001k also to the ACS section 82-2 where notation bm1001k denotes branch-metric data corresponding to a state transition occurring over two time slots. By the same token, the branch-metric computation section 81-6 computes branch-metric data bm0110k (=bm011k-1+bm110k) and outputs the branch-metric data bm0110k to the ACS section 82-3 where notation bm0110k denotes branch-metric data corresponding to a state transition occurring over two time slots. In the same way, the branch-metric computation section 81-7 computes branch-metric data bm1110k (=bm111k-1+bm110k) and outputs the branch-metric data bm1110k also to the ACS section 82-3 where notation bm1110k denotes branch-metric data corresponding to a state transition occurring over two time slots.
Similarly, the branch-metric computation section 81-8 computes branch-metric data bm0011k (=bm001k-1+bm011k) and outputs the branch-metric data bm0011k to the ACS section 82-4 where notation bm0011k denotes branch-metric data corresponding to a state transition occurring over two time slots. Likewise, the branch-metric computation section 81-9 computes branch-metric data bm0111k (=bm011k-1+bm111k) and outputs the branch-metric data bm0111k also to the ACS section 82-4 where notation bm0111k denotes branch-metric data corresponding to a state transition occurring over two time slots. By the same token, the branch-metric computation section 81-10 computes branch-metric data bm1111k (=bm111k-1+bm111k) and outputs the branch-metric data bm111k also to the ACS section 82-4 where notation bm1111k denotes branch-metric data corresponding to a state transition occurring over two time slots.
The ACS circuit 42 adds path-metric data stored internally as path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data received from the branch-metric computation circuit 41 to produce a sum. If paths merge at the path memory 43, the ACS circuit 42 adds path-metric data of a state immediately leading ahead of a state immediately preceding the present state to branch-metric data received from the branch-metric computation circuit 41 to produce a sum for each of the merging paths, and compares the sums with each other to select the smallest one. The ACS circuit 42 then uses the sum or the smallest sum as updated path-metric data m of the present state. The path-metric data m is the likelihood of a history up to state S. The ACS circuit 42 includes as many ACS sections 82 as states. In the case of the typical configuration shown in FIG. 9, the number of states is 4. Thus, the ACS circuit 42 includes 4 ACS sections 82-1 to 82-4.
The ACS section 82-1 updates the path-metric data m00k, which is the likelihood of a history up to state S00. To be more specific, the ACS section 82-1 adds the path-metric data m00k-2 stored internally in the ACS section 82-1 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm0000k received from the branch-metric computation section 81-1 to produce a first sum. The ACS section 82-1 also adds the path-metric data m10k-2 stored internally in the ACS section 82-3 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm1000k received from the branch-metric computation section 81-2 to produce a second sum. In addition, the ACS section 82-1 also adds the path-metric data m11k-2 stored internally in the ACS section 82-4 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm1100k received from the branch-metric computation section 81-3 to produce a third sum. Then, the ACS section 82-1 compares the first, second and third sums with each other in order to select the smallest one to be used as updated path-metric data m00k of the present state. Finally, the ACS section 82-1 outputs a selection result sel00 to a memory included in the path memory 43 as a memory used for storing the value of state S00. The computations and the comparison, which are carried out by the ACS section 82-1, can be expressed by Eq. (11) given as follows:m00k=min {m00k-2+bm0000k, m10k-2+bm1000k, m11k-2+bm1100k}  (11)
Likewise, the ACS section 82-2 updates the path-metric data m01k, which is the likelihood of a history up to state S01. To be more specific, the ACS section 82-2 adds the path-metric data m00k-2 stored internally in the ACS section 82-1 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm0001k received from the branch-metric computation section 81-4 to produce a first sum. The ACS section 82-2 also adds the path-metric data m10k-2 stored internally in the ACS section 82-3 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm1001k received from the branch-metric computation section 81-5 to produce a second sum. Then, the ACS section 82-2 compares the first and second sums with each other in order to select the smaller one to be used as updated path-metric data m01k of the present state. Finally, the ACS section 82-2 outputs a selection result sel01 to a memory included in the path memory 43 as a memory used for storing the value of state S01. The computations and the comparison, which are carried out by the ACS section 82-2, can be expressed by Eq. (12) given as follows:m01k=min {m00k-2+bm0001k, m10k-2+bm1001k}  (12)
By the same token, the ACS section 82-3 updates the path-metric data m10k, which is the likelihood of a history up to state S10. To be more specific, the ACS section 82-3 adds the path-metric data m11k-2 stored internally in the ACS section 82-4 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm1110k received from the branch-metric computation section 81-7 to produce a first sum. The ACS section 82-3 also adds the path-metric data m01k-2 stored internally in the ACS section 82-2 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm0110k received from the branch-metric computation section 81-6 to produce a second sum. Then, the ACS section 82-3 compares the first and second sums with each other in order to select the smaller one to be used as updated path-metric data m10k of the present state. Finally, the ACS section 82-3 outputs a selection result sel10 to a memory included in the path memory 43 as a memory used for storing the value of state S10. The computations and the comparison, which are carried out by the ACS section 82-3, can be expressed by Eq. (13) given as follows:m10k=min {m11k-2+bm1110k, m01k-2+bm0110k}  (13)
The ACS section 82-4 updates the path-metric data m11k, which is the likelihood of a history up to state S11. To be more specific, the ACS section 82-4 adds the path-metric data m11k-2 stored internally in the ACS section 82-4 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm1111k received from the branch-metric computation section 81-10 to produce a first sum. The ACS section 82-4 also adds the path-metric data m01k-2 stored internally in the ACS section 82-2 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm0111k received from the branch-metric computation section 81-9 to produce a second sum. In addition, the ACS section 82-4 also adds the path-metric data m00k-2 stored internally in the ACS section 82-1 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm0011k received from the branch-metric computation section 81-8 to produce a third sum. Then, the ACS section 82-4 compares the first, second and third sums with each other in order to select the smallest one to be used as updated path-metric data m11k of the present state. Finally, the ACS section 82-4 outputs a selection result sel11 to a memory included in the path memory 43 as a memory used for storing the value of state S11. The computations and the comparison, which are carried out by the ACS section 82-1, can be expressed by Eq. (14) given as follows:m11k=min {m11k-2+bm1111k, m01k-2+bm0111k, m00k-2+bm0011k}  (14)
A trellis depicted in the path memory 43 of the typical configuration shown in FIG. 10 has only one stage. The number of states is the same as that for the trellis depicted in the path memory 43 shown in FIG. 6. However, the select and shift operations are carried out for every 2 bits (that is, for every two time slots).
The trellis depicted in the path memory 43 shown in FIG. 10 indicates that it is quite within the bounds of possibility that a transition occurs from state S00 to state S00, S01 or S11 at a time immediately following the next time, a transition occurs from state S01 to state S10 or S11 at a time immediately following the next time, a transition occurs from state S10 to state S00 or S01 at a time immediately following the next time and a transition occurs from state S11 to state S00, S10 or S11 at a time immediately following the next time. That is to say, the Viterbi decoding circuit 19 of this case carries out a decoding process on the basis of the trellis expressing a state-transition diagram shown in FIG. 3 as a state-transition diagram of the PR (1, x, 1) transmission line in terms of sequences along the time axis based on units of two time slots.
Thus, in the path memory 43 shown in FIG. 10, a value to be stored instantly in a memory for state S00 at any specific stage is a value selected among a value stored in a memory for state S00 at a stage immediately preceding the specific stage, a value stored in a memory for state S10 at a stage immediately preceding the specific stage and a value stored in a memory for state S11 at the stage immediately preceding the specific stage in accordance with a selection result sel00 received from the ACS section 82-1. The selected value stored instantly in the memory for state S00 at the specific stage is shifted in the same time slot to a memory for state S00 at a stage immediately following the specific stage, a memory for state S01 at a stage immediately following the specific stage and a memory for state S11 at the stage immediately following the specific stage. Similarly, in the path memory 43, a value to be stored instantly in a memory for state S00 at any specific stage is a value selected among a value stored in a memory for state S00 at a stage immediately preceding the specific stage and a value stored in a memory for state S10 at the stage immediately preceding the specific stage in accordance with a selection result sel01 received from the ACS section 82-2. The selected value stored instantly in the memory for state S01 at the specific stage is shifted in the same time slot to a memory for state S10 at a stage immediately following the specific stage and a memory for state S11 at the stage immediately following the specific stage.
By the same token, in the path memory 43, a value to be stored instantly in a memory for state S10 at any specific stage is a value selected among a value stored in a memory for state S01 at a stage immediately preceding the specific stage and a value stored in a memory for state S11 at the stage immediately preceding the specific stage in accordance with a selection result sel10 received from the ACS section 82-3. The selected value stored instantly in the memory for state S10 at the specific stage is shifted in the same time slot to a memory for state S00 at a stage immediately following the specific stage and a memory for state S01 at the stage immediately following the specific stage. In the same way as stage S00, in the path memory 43, a value to be stored instantly in a memory for state S11 at any specific stage is a value selected among a value stored in a memory for state S00 at a stage immediately preceding the specific stage, a value stored in a memory for state S01 at a stage immediately preceding the specific stage and a value stored in a memory for state S11 at the stage immediately preceding the specific stage in accordance with a selection result sel11 received from the ACS section 82-4. The selected value stored instantly in the memory for state S11 at the specific stage is shifted in the same time slot to a memory for state S00 at a stage immediately following the specific stage, a memory for state S10 at a stage immediately following the specific stage and a memory for state S11 at the stage immediately following the specific stage. As a result, data of two time slots is output to the demodulation circuit 20 as the modulated sequence xt.
As is obvious from the above descriptions, the number of branch-metric computation sections increases from 6 in the branch-metric computation circuit 41 shown in FIG. 5 to 10 in the branch-metric computation circuit 41 shown in FIG. 9. However, the number of states employed the ACS circuit 42 remains at 4 as it is. Thus, the number of ACS sections employed in the ACS circuit 42 shown in FIG. 9 also remains the same as that for the ACS circuit 42 shown in FIG. 5. Nevertheless, the number of states preceding the present state by two time slots for the ACS circuit 42 shown in FIG. 9 increases to 3 from 2 states preceding the present state by one time slot for the ACS circuit 42 shown in FIG. 5. Thus, in the ACS circuit 42 shown in FIG. 9, the smallest one among 3 different results of addition is selected as path-metric data.
That is to say, the Viterbi decoding circuit 19 shown in FIGS. 9 and 10 as a Viterbi decoding circuit 19 for carrying out processing of an amount corresponding to two time slots of the configurations shown in FIGS. 5 and 6 in just one time slot has a circuit size much larger than that of the Viterbi decoding circuit 19 shown in FIGS. 5 and 6 as a Viterbi decoding circuit 19 for carrying out processing of one time slot.
FIGS. 11 and 12 are diagrams showing a Viterbi decoding circuit 19 provided for the PR (1, x, x, 1) transmission line shown in FIG. 4 as a Viterbi decoding circuit 19 capable of carrying out processing of the amount corresponding to two time slots of the configurations shown in FIGS. 7 and 8 in just one time slot. That is to say, the Viterbi decoding circuit 19 shown in FIGS. 11 and 12 is capable of carrying out processing, which is performed by the Viterbi decoding circuit 19 shown in FIGS. 7 and 8 in two time slots, in just one time slot.
In addition, the Viterbi decoding circuit 19 shown in FIGS. 11 and 12 is different from the Viterbi decoding circuit 19 shown in FIGS. 9 and 10 only in that the number of states increases to 6 from 4 for the Viterbi decoding circuit 19 shown in FIGS. 9 and 10 whereas the number of state transitions in the Viterbi decoding circuit 19 shown in FIGS. 11 and 12 increases to 16 from 10 for the Viterbi decoding circuit 19 shown in FIGS. 9 and 10. Thus, the Viterbi decoding circuit 19 shown in FIGS. 11 and 12 basically has a configuration identical with that of the Viterbi decoding circuit 19 shown in FIGS. 9 and 10, making it unnecessary to explain the Viterbi decoding circuit 19 shown in FIGS. 11 and 12 in detail.
That is to say, the branch-metric computation circuit 41 shown in FIG. 11 has branch-metric computation sections 91-1 through 91-16 each used for computing branch-metric data corresponding to a state transition occurring over two time slots from a state immediately leading ahead of a state immediately preceding the present state.
The branch-metric computation section 91-1 computes branch-metric data bm00000k=0000k-1+bm0000k and outputs the branch-metric data bm00000k to the ACS section 92-1 where notation bm00000k denotes branch-metric data corresponding to a state transition occurring over two time slots in the configuration shown in FIG. 7. By the same token, the branch-metric computation section 91-2 computes branch-metric data bm10000k=1000k-1+bm0000k and outputs the branch-metric data bm10000k also to the ACS section 92-1 where notation bm10000k denotes branch-metric data corresponding to a state transition occurring over two time slots. In the same way, the branch-metric computation section 91-3 computes branch-metric data bm11000k=1100k-1+bm1000k and outputs the branch-metric data bm11000k also to the ACS section 92-1 where notation bm11000k denotes branch-metric data corresponding to a state transition occurring over two time slots.
Likewise, the branch-metric computation section 91-4 computes branch-metric data bm00001k=0000k-1+bm0001k and outputs the branch-metric data bm00001k to the ACS section 92-2 where notation bm00001k denotes branch-metric data corresponding to a state transition occurring over two time slots. By the same token, the branch-metric computation section 91-5 computes branch-metric data bm10001k=1000k-1+bm0001k and outputs the branch-metric data bm10001k also to the ACS section 92-2 where notation bm10001k denotes branch-metric data corresponding to a state transition occurring over two time slots. In the same way, the branch-metric computation section 91-6 computes branch-metric data bm11001k=1100k-1+bm1001k and outputs the branch-metric data bm11001k also to the ACS section 92-2 where notation bm11001k denotes branch-metric data corresponding to a state transition occurring over two time slots.
Likewise, the branch-metric computation section 91-7 computes branch-metric data bm00011k=0001k-1+bm0011k and outputs the branch-metric data bm00011k to the ACS section 92-3 where notation bm00011k denotes branch-metric data corresponding to a state transition occurring over two time slots. By the same token, the branch-metric computation section 91-8 computes branch-metric data bm10011k=1001k-1+bm0001k and outputs the branch-metric data bm10011k also to the ACS section 92-3 where notation bm10011k denotes branch-metric data corresponding to a state transition occurring over two time slots. In the same way, the branch-metric computation section 91-9 computes branch-metric data bm01100k=0110k-1+bm1100k and outputs the branch-metric data bm01100k to the ACS section 92-4 where notation bm01100k denotes branch-metric data corresponding to a state transition occurring over two time slots. Similarly, the branch-metric computation section 91-10 computes branch-metric data bm11100k=1110k-1+bm1100k and outputs the branch-metric data bm11100k also to the ACS section 92-4 where notation bm11100k denotes branch-metric data corresponding to a state transition occurring over two time slots.
Likewise, the branch-metric computation section 91-11 computes branch-metric data bm00110k=0011k-1+bm0110k and outputs the branch-metric data bm00110k to the ACS section 92-5 where notation bm00110k denotes branch-metric data corresponding to a state transition occurring over two time slots. By the same token, the branch-metric computation section 91-12 computes branch-metric data bm01110k=0111k-1+bm1110k and outputs the branch-metric data bm01110k also to the ACS section 92-5 where notation bm01110k denotes branch-metric data corresponding to a state transition occurring over two time slots. In the same way, the branch-metric computation section 91-13 computes branch-metric data bm11110k=1111k-1+bm1110k and outputs the branch-metric data bm11110k also to the ACS section 92-5 where notation bm11110k denotes branch-metric data corresponding to a state transition occurring over two time slots.
Likewise, the branch-metric computation section 91-14 computes branch-metric data bm00111k=0011k-1+bm0111k and outputs the branch-metric data bm00111k to the ACS section 92-6 where notation bm00111k denotes branch-metric data corresponding to a state transition occurring over two time slots. By the same token, the branch-metric computation section 91-15 computes branch-metric data bm01111k=0111k-1+bm1111k and outputs the branch-metric data bm01111k also to the ACS section 92-6 where notation bm01111k denotes branch-metric data corresponding to a state transition occurring over two time slots. In the same way, the branch-metric computation section 91-16 computes branch-metric data bm11111k=1111k-1+bm1111k and outputs the branch-metric data bm11111k also to the ACS section 92-6 where notation bm11111k denotes branch-metric data corresponding to a state transition occurring over two time slots.
The ACS circuit 42 adds path-metric data stored internally as path-metric data of a state immediately leading ahead of the state immediately preceding the present state to branch-metric data received from the branch-metric computation circuit 41 to produce a sum. If paths merge in the path memory 43, the ACS circuit 42 adds path-metric data of a state immediately leading ahead of a state immediately preceding the present state to branch-metric data received from the branch-metric computation circuit 41 to produce a sum for each of the merging paths, and compares the sums with each other to select the smallest one. The ACS circuit 42 then uses the sum or the selected smallest sum as updated path-metric data m of the present state. The path-metric data m is the likelihood of a history up to state S. The ACS circuit 42 includes as many ACS (add, compare and select) sections 62 as states. In the case of the typical configuration shown in FIG. 11, the number of states is 6. Thus, the ACS circuit 42 includes 6 ACS sections 92-1 to 92-6.
To put it concretely, the ACS section 92-1 updates the path-metric data m000k, which is the likelihood of a history up to state S000. To be more specific, the ACS section 92-1 adds the path-metric data m000k-2 stored internally in the ACS section 92-1 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm00000k received from the branch-metric computation section 91-1 to produce a first sum. The ACS section 92-1 also adds the path-metric data m100k-2 stored internally in the ACS section 92-4 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm10000k received from the branch-metric computation section 91-2 to produce a second sum. In addition, the ACS section 92-1 also adds the path-metric data m110k-2 stored internally in the ACS section 92-5 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm11000k received from the branch-metric computation section 91-3 to produce a third sum. Then, the ACS section 92-1 compares the first, second and third sums with each other in order to select the smallest one to be used as updated path-metric data m000k of the present state. Finally, the ACS section 92-1 outputs a selection result sel000 to a memory included in the path memory 43 as a memory used for storing the value of state S000. The computations and the comparison, which are carried out by the ACS section 92-1, can be expressed by Eq. (15) given as follows:m000k=min {m000k-2+bm00000k, m100k-2+bm10000k, m110k-2+bm11000k}  (15)
By the same token, the ACS section 92-2 updates the path-metric data m001k, which is the likelihood of a history up to state S001. To be more specific, the ACS section 92-2 adds the path-metric data m000k-2 stored internally in the ACS section 92-1 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm00001k received from the branch-metric computation section 91-4 to produce a first sum. The ACS section 92-2 also adds the path-metric data m100k-2 stored internally in the ACS section 92-4 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm10001k received from the branch-metric computation section 91-5 to produce a second sum. In addition, the ACS section 92-2 also adds the path-metric data m110k-2 stored internally in the ACS section 92-5 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm11001k received from the branch-metric computation section 91-6 to produce a third sum. Then, the ACS section 92-2 compares the first, second and third sums with each other in order to select the smallest one to be used as updated path-metric data m001k of the present state. Finally, the ACS section 92-2 outputs a selection result sel001 to a memory included in the path memory 43 as a memory used for storing the value of state S001. The computations and the comparison, which are carried out by the ACS section 92-2, can be expressed by Eq. (16) given as follows:m001k=min {m000k-2+bm00001k, m100k-2+bm10001k, m110k-2+bm11001k}  (16)
Likewise, the ACS section 92-3 updates the path-metric data m011k, which is the likelihood of a history up to state S011. To be more specific, the ACS section 92-3 adds the path-metric data m000k-2 stored internally in the ACS section 92-1 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm00011k received from the branch-metric computation section 91-7 to produce a first sum. The ACS section 92-3 also adds the path-metric data m100k-2 stored internally in the ACS section 92-4 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm10011k received from the branch-metric computation section 91-8 to produce a second sum. Then, the ACS section 92-3 compares the first and second sums with each other in order to select the smaller one to be used as updated path-metric data m011k of the present state. Finally, the ACS section 92-3 outputs a selection result sel011 to a memory included in the path memory 43 as a memory used for storing the value of state S011. The computations and the comparison, which are carried out by the ACS section 92-3, can be expressed by Eq. (17) given as follows:m011k=min {m000k-2+bm00011k, m100k-2+bm10011k}  (17)
By the same token, the ACS section 92-4 updates the path-metric data m100k, which is the likelihood of a history up to state S100. To be more specific, the ACS section 92-4 adds the path-metric data m111k-2 stored internally in the ACS section 92-6 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm11100k received from the branch-metric computation section 91-10 to produce a first sum. The ACS section 92-4 also adds the path-metric data m011k-2 stored internally in the ACS section 92-3 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm01100k received from the branch-metric computation section 91-9 to produce a second sum. Then, the ACS section 92-4 compares the first and second sums with each other in order to select the smaller one to be used as updated path-metric data m100k of the present state. Finally, the ACS section 92-4 outputs a selection result sel100 to a memory included in the path memory 43 as a memory used for storing the value of state S100. The computations and the comparison, which are carried out by the ACS section 92-4, can be expressed by Eq. (18) given as follows:m100k=min {m111k-2+bm11100k, m011k-2+bm01100k}  (18)
In the same way as the ACS section 92-1, the ACS section 92-5 updates the path-metric data m110k, which is the likelihood of a history up to state S110. To be more specific, the ACS section 92-5 adds the path-metric data m111k-2 stored internally in the ACS section 92-6 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm11110k received from the branch-metric computation section 91-13 to produce a first sum. The ACS section 92-5 also adds the path-metric data m011k-2 stored internally in the ACS section 92-3 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm01110k received from the branch-metric computation section 91-12 to produce a second sum. In addition, the ACS section 92-5 also adds the path-metric data m001k-2 stored internally in the ACS section 92-2 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm00110k received from the branch-metric computation section 91-11 to produce a third sum. Then, the ACS section 92-5 compares the first, second and third sums with each other in order to select the smallest one to be used as updated path-metric data m110k of the present state. Finally, the ACS section 92-5 outputs a selection result sel110 to a memory included in the path memory 43 as a memory used for storing the value of state S110. The computations and the comparison, which are carried out by the ACS section 92-5, can be expressed by Eq. (19) given as follows:m110k=min {m111k-2+bm11110k, m011k-2+bm01110k, m001k-2+bm00110k}  (19)
By the same token, the ACS section 92-6 updates the path-metric data m111k, which is the likelihood of a history up to state S111. To be more specific, the ACS section 92-6 adds the path-metric data m111k-2 stored internally in the ACS section 92-6 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm11111k received from the branch-metric computation section 91-16 to produce a first sum. The ACS section 92-6 also adds the path-metric data m011k-2 stored internally in the ACS section 92-3 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm01111k received from the branch-metric computation section 91-15 to produce a second sum. In addition, the ACS section 92-6 also adds the path-metric data m001k-2 stored internally in the ACS section 92-2 as the path-metric data of a state immediately leading ahead of the state immediately preceding the present state to the branch-metric data bm00111k received from the branch-metric computation section 91-14 to produce a third sum. Then, the ACS section 92-6 compares the first, second and third sums with each other in order to select the smallest one to be used as updated path-metric data m111k of the present state. Finally, the ACS section 92-6 outputs a selection result sel111 to a memory included in the path memory 43 as a memory used for storing the value of state S111. The computations and the comparison, which are carried out by the ACS section 92-6, can be expressed by Eq. (20) given as follows:m111k=min {m111k-2+bm11111k, m011k-2+bm01111k, m001k-2+bm00111k}  (20)
A trellis depicted in the path memory 43 of the typical configuration shown in FIG. 12 has only 1 stage. The number of states is the same as that for the trellis depicted in the path memory 43 shown in FIG. 8. However, the select and shift operations are carried out for every 2 bits (that is, for every two time slots).
The trellis depicted in the path memory 43 shown in FIG. 12 indicates that it is quite within the bounds of possibility that a transition occurs from state S000 to state S000, S001 or S011 at a time following the next time, a transition occurs from state S001 to state S110 or Sill at a time following the next time, a transition occurs from state S011 to state S100, S110 or S111 at a time following the next time, a transition occurs from state S100 to state S000, S001 or S011 at a time following the next time, a transition occurs from state S110 to state S000 or S001 at a time following the next time and a transition occurs from state S111 to state S100, S110 or S111 at a time following the next time. That is to say, the Viterbi decoding circuit 19 of this case carries out a decoding process on the basis of the trellis expressing a state-transition diagram shown in FIG. 4 as a state-transition diagram of the PR (1, x, x, 1) transmission line in terms of sequences along the time axis based on two time slots.
Thus, in the path memory 43, a value to be stored instantly in a memory for state S000 at any specific stage is a value selected among a value stored in a memory for state S000 at a stage immediately preceding the specific stage, a value stored in a memory for state S100 at a stage immediately preceding the specific stage and a value stored in a memory for state S110 at the stage immediately preceding the specific stage in accordance with a selection result sel000 received from the ACS section 92-1. The selected value stored instantly in the memory for state S000 at the specific stage is shifted in the same time slot to a memory for state S000 at a stage immediately following the specific stage, a memory for state S000 at a stage immediately following the specific stage and a memory for state S011 at the stage immediately following the specific stage. Similarly, in the path memory 43, a value to be stored instantly in a memory for state S000 at any specific stage is a value selected among a value stored in a memory for state S000 at a stage immediately preceding the specific stage, a value stored in a memory for state S100 at a stage immediately preceding the specific stage and a value stored in a memory for state S110 at the stage immediately preceding the specific stage in accordance with a selection result sel001 received from the ACS section 92-2. The selected value stored instantly in the memory for state S001 at the specific stage is shifted in the same time slot to a memory for state S110 at a stage immediately following the specific stage and a memory for state S111 at the stage immediately following the specific stage.
By the same token, in the path memory 43, a value to be stored instantly in a memory for state S011 at any specific stage is a value selected among a value stored in a memory for state S000 at a stage immediately preceding the specific stage and a value stored in a memory for state S100 at the stage immediately preceding the specific stage in accordance with a selection result sel011 received from the ACS section 92-3. The selected value stored instantly in the memory for state S011 at the specific stage is shifted in the same time slot to a memory for state S100 at a stage immediately following the specific stage, a memory for state S110 at a stage immediately following the specific stage and a memory for state S111 at the stage immediately following the specific stage. In the same way, in the path memory 43, a value to be stored instantly in a memory for state S100 at any specific stage is a value selected among a value stored in a memory for state S011 at a stage immediately preceding the specific stage and a value stored in a memory for state S111 at the stage immediately preceding the specific stage in accordance with a selection result sel100 received from the ACS section 92-4. The selected value stored instantly in the memory for state S100 at the specific stage is shifted in the same time slot to a memory for state S000 at a stage immediately following the specific stage, a memory for state S001 at a stage immediately following the specific stage and a memory for state S011 at the stage immediately following the specific stage.
By the same token, in the path memory 43, a value to be stored instantly in a memory for state S110 at any specific stage is a value selected among a value stored in a memory for state S001 at a stage immediately preceding the specific stage, a memory for state S011 at a stage immediately preceding the specific stage and a value stored in a memory for state S111 at the stage immediately preceding the specific stage in accordance with a selection result sel110 received from the ACS section 92-5. The selected value stored instantly in the memory for state S110 at the specific stage is shifted in the same time slot to a memory for state S000 at a stage immediately following the specific stage and a memory for state S001 at the stage immediately following the specific stage. In the same way, in the path memory 43, a value to be stored instantly in a memory for state S111 at any specific stage is a value selected among a value stored in a memory for state S001 at a stage immediately preceding the specific stage, a memory for state S011 at a stage immediately preceding the specific stage and a value stored in a memory for state S111 at the stage immediately preceding the specific stage in accordance with a selection result sel111 received from the ACS section 92-6. The selected value stored instantly in the memory for state S111 at the specific stage is shifted in the same time slot to a memory for state S100 at a stage immediately following the specific stage, a memory for state S110 at a stage immediately following the specific stage and a memory for state S111 at the stage immediately following the specific stage. As a result, data of two time slots is output to the demodulation circuit 20 as the modulated sequence xt.
As is obvious from the above descriptions, the number of branch-metric computation sections increases from 10 in the branch-metric computation circuit 41 shown in FIG. 7 to 16 in the branch-metric computation circuit 41 shown in FIG. 11. However, the number of states for the transmission line remains at 6 as it is. Thus, the number of ACS sections employed in the ACS circuit 42 shown in FIG. 11 also remains the same as that for the ACS circuit 42 shown in FIG. 7. However, the number of states preceding the present state by two time slots for the ACS circuit 42 shown in FIG. 11 increases to three from two states preceding the present state by one time slot for the ACS circuit 42 shown in FIG. 7. Thus, in the ACS circuit 42 shown in FIG. 11, the smallest one among 3 different results of addition is selected as path-metric data.
That is to say, the Viterbi decoding circuit 19 shown in FIGS. 11 and 12 for carrying out processing having an amount corresponding to two time slots in the Viterbi decoding circuit 19 shown in FIGS. 7 and 8 in just one time slot has a circuit size much larger than that of the Viterbi decoding circuit 19 shown in FIGS. 7 and 8 for carrying out processing of one time slot.
It is to be noted that descriptions with reference to FIGS. 1 to 12 are applicable and properly referred to in the following explanation of the present invention.